package merge56;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Merge {
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if(len<2){
            return intervals;
        }

        //按元素的左边界排序
        Arrays.sort(intervals, Comparator.comparingInt(ints ->ints[0]));
        List<int[]> res = new ArrayList<>();

        res.add(intervals[0]);

        for (int i = 1; i < len; i++) {
            int[] cur = intervals[i];
            int[] peek = res.get(res.size() - 1); //放入list中的，也是前一个元素
            if(cur[0] > peek[1]){
                //无重复
                res.add(cur);
            }else{
                peek[1] = Math.max(peek[1], cur[1]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }

    public static void main(String[] args) {
        Merge merge = new Merge();

        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] res = merge.merge(intervals);
        for (int i = 0; i < res.length; i++) {
            System.out.println(Arrays.toString(res[i]));
        }

    }
}
